import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Solution212 {
    int[][] dir=new int[][]{{1,0},{-1,0},{0,1},{0,-1}};

    public List<String> findWords(char[][] board, String[] words) {
        Trie trie=new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        List<String> strings=new ArrayList<>();
        for (int i=0;i<board.length;i++){
            for (int j=0;j<board[i].length;j++){
                dfs(board,trie,i,j,strings);
            }
        }
        return strings;
    }

    public void dfs(char[][] board,Trie now,int i,int j,List<String> ans){
        char c=board[i][j];
        if (!now.children.containsKey(c)){
            return;
        }
        Trie next=now.children.get(c);
        if (!next.word.equals("")){
            ans.add(next.word);
            next.word="";
        }
        if (!next.children.isEmpty()){
            board[i][j]='#';
            for (int[] ints : dir) {
                int i1=i+ints[0];
                int j1=j+ints[1];
                if (i1>=0&&i1<board.length&&j1>=0&&j1<board[0].length){
                    dfs(board,next,i1,j1,ans);
                }
            }
            board[i][j]=c;
        }
        if (next.children.isEmpty()){
            now.children.remove(c);
        }
    }

    public static class Trie{
        Map<Character,Trie> children;
        String word;

        public Trie() {
            children=new HashMap<>();
            word="";
        }

        public void insert(String word){
            Trie now=this;
            for (int i=0;i<word.length();i++){
                char c=word.charAt(i);
                if (!now.children.containsKey(c)){
                    now.children.put(c,new Trie());
                }
                now=now.children.get(c);
            }
            now.word=word;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution212().findWords(new char[][]{{'o','a','a','n'},{'e','t','a','e'},{'i','h','k','r'},{'i','f','l','v'}},new String[]{"oath","pea","eat","rain"}));
    }
}
